package BackTrack.Medium;

import java.util.*;

public class LC0216 {
    class Path {
        LinkedList<Integer> array = new LinkedList<>();
        int sum = 0;

        int add(int i) {
            array.add(i);
            sum += i;
            return sum;
        }

        int removeLast() {
            int last = array.removeLast();
            sum -= last;
            return sum;
        }
    }

    Set<Set<Integer>> combinations = new HashSet<>();
    int n, k;

    public List<List<Integer>> combinationSum3(int k, int n) {
        this.n = n;
        this.k = k;
        boolean[] available = new boolean[10];
        for (int i = 0; i < 10; i++) available[i] = true;
        backTrack(null, available);

        List<List<Integer>> ret = new ArrayList<>();
        for (Set<Integer> set : combinations) {
            ret.add(new ArrayList<>(set));
        }
        return ret;
    }

    private void backTrack(Path path, boolean[] available) {
        if (path == null) path = new Path();
        int start = path.array.size() > 0 ? path.array.getLast() + 1 : 1;
        // i的上限可以剪枝：如果i超过 9 + 1 - (k - path.array.size())，那么向下搜索必然不满足k的条件（剩下可用的数字过少；注意下一层只会搜索大于i的数字）
        for (int i = start; i <= 9 + 1 - (k - path.array.size()); i++) {
            if (available[i]) {
                available[i] = false;
                int sum = path.add(i);
                if (sum <= n) {
                    if (sum < n) {
                        if (path.array.size() < k) backTrack(path, available); // 只有尚未取到k个数字时允许向下扩展
                        path.removeLast(); // 否则尝试下一个数字
                        available[i] = true;
                    }
                    else { // sum==n
                        if (path.array.size() == k) combinations.add(new HashSet<>(path.array));
                        path.removeLast();
                        available[i] = true;
                        break; // for循环不必再继续
                    }
                }
                else {
                    path.removeLast();
                    available[i] = true;
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int k = 3, n = 9;
        LC0216 solution = new LC0216();
        List<List<Integer>> ret = solution.combinationSum3(k, n);
        System.out.println();
    }
}
